package Queue;

public class BigTopPile<E extends Priority> implements Queue<E>{

    private Priority[] arr;
    private int size;

    public BigTopPile() {
    }

    public BigTopPile(int capacity) {
        arr = new Priority[capacity];
    }

    @Override
    public boolean offer(E value) {
        if (isFull()) {
            return false;
        }
        int i = size++;
        int j = (i - 1) / 2;
        while (i > 0 && arr[j].priority() < value.priority()) {
            arr[i] = arr[j];
            i = j;
            j = (i - 1) / 2;
        }
/*        if (j == 0) {
            arr[i] = arr[j];
            arr[j] = value;
        }
        if (arr[j].priority() > value.priority() ) {
            arr[i] = value;
        }*/
        arr[i] = value;
        return true;
    }

    @Override
    public E poll() {
        if (isEmpty()) {
            return null;
        }

        E ret = (E)arr[0];
        arr[0] = arr[size - 1];

        arr[size] = null;
        int i = 0;
        int j = 0;
        while ( (i * 2 + 1) < size && (i * 2 + 2) < size && arr[i].priority() < arr[2*i + 1].priority() && arr[i].priority() < arr[2*i + 2].priority()) {
            E left = (E)arr[i*2 + 1];
            E right = (E)arr[i*2 + 2];
            if (left.priority() > right.priority()) {
                j = i * 2 + 1;
            }else {
                j = i * 2 + 2;
            }
            E temp = (E)arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i = j;
        }
        size--;
        return ret;
    }

    @Override
    public E peek() {
        return null;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean isFull() {
        return size == arr.length;
    }
}
